Embodiments of the invention relates generally to the field of computer systems, and more particularly to digital encoding.
A Gray code is a binary code in which sequential numbers of the code differ by only one bit. For example, each sequential number in the following Gray code sequence differs by one bit 00, 01, 11, 10.
Because a Gray code sequence has the property that sequential numbers of the code differ by only one bit, a Gray code is very useful in many digital circuits. For example, Gray codes are often used in a computer system to address sequential memory, resulting in less power usage and simplified error correction of the addresses. Gray codes are also used in circuits involving multiple clock domains, for example—for FIFOs used as buffers, and the storage of pixels in digital imagery systems such as high definition televisions, digital cameras, and the like.
A Gray code sequence is comprised of Gray codes. Table 1 illustrates the binary numbers 00 through 11 and their corresponding Gray codes.
TABLE 1Gray codes for binary numbers 00-11Binary CodeGray Code0000010110111110
Note that the property that each sequential number of a Gray code sequence differs by only one bit applies also to a transition from the last number of a Gray code sequence back to the first number of the sequence. Table 1 is an example of such a Gray code sequence, where the transition from the last Gray code in the sequence (“10”) differs by only one bit from the first number in the sequence (“00”).
The application of Gray codes work well for sequences having a length “L” which can be expressed as a power of 2. For example, Table 1 illustrates a Gray code sequence for a sequence of length (“L”) equal to 4. In sequences were L is as a power of 2, the Gray code sequence exhibits the property that the last number in the sequence and the first number in the sequence differ by only one bit.
For sequences having a length which is an odd positive integer and utilizing traditional methods and apparatus of generating Gray code sequences, the resulting Gray code sequence will not have sequential Gray codes which differ by only one bit. Thus, for binary sequences of an odd length, the corresponding Gray code sequence cannot transition from the last Gray code to the first Gray code and still maintain the Gray code property for the transition.
What is needed, then, is a method and apparatus to generate a Gray code sequence for “L” binary values, where “L” is an odd positive integer.